package Dict;

public class DictHT {
    private final DictEntry[] table; // entry数组
    private final int size; // hash表大小
    private final int sizemask; // hash表大小-1
    private int used; // entry个数

    public DictHT(int size) {
        this.table = new DictEntry[size];
        this.size = size;
        this.sizemask = size - 1;
    }

    public DictEntry[] getTable() {
        return table;
    }

    public int getSize() {
        return size;
    }

    public int getUsed() {
        return used;
    }

    public void setUsed(int used) {
        this.used = used;
    }

    // 插入
    public void insert(String key, Object value) {
        int index = hashIndex(key);
        DictEntry entry = new DictEntry(key, value);

        // 处理hash冲突，使用拉链法
        if (table[index] == null) {
            table[index] = entry;
        } else {
            DictEntry currentEntry = table[index];
            while (currentEntry.next != null) {
                // 如果找到相同的key，则更新value，即覆盖原来元素
                if (currentEntry.getKey().equals(key)) {
                    currentEntry.setValue((String) value);
                    return;
                }

                // 向后移动工作指针
                currentEntry = currentEntry.next;
            }

            // 如果没有找到相同的key，则将新的entry添加到链表的末尾
            currentEntry.next = entry;
        }
        used++;
    }

    // 查找
    public String find(String key) {
        int index = hashIndex(key);
        DictEntry entry = table[index];
        while (entry != null) {
            if (entry.getKey().equals(key)) {
                return (String) entry.getValue();
            }
            entry = entry.next;
        }
        return null;
    }

    // 根据hash值计算索引
    public int hashIndex(String key) {
        return key.hashCode() & sizemask;
    }
}
